package com.ztom.top100;

import java.util.HashSet;
import java.util.Set;

/**
 * 相交链表
 * <p>
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 *
 * @author ZhangTao
 */
public class Code56GetIntersectionNode {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 长的先走差值步
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int l1 = 0;
        ListNode tmp1 = headA;
        while (tmp1 != null) {
            l1++;
            tmp1 = tmp1.next;
        }
        int l2 = 0;
        ListNode tmp2 = headB;
        while (tmp2 != null) {
            l2++;
            tmp2 = tmp2.next;
        }

        tmp1 = headA;
        tmp2 = headB;
        if (l1 >= l2) {
            for (int i = 0; i < l1 - l2; i++) {
                tmp1 = tmp1.next;
            }
        } else {
            for (int i = 0; i < l2 - l1; i++) {
                tmp2 = tmp2.next;
            }
        }
        while (tmp1 != null && tmp2 != null) {
            if (tmp1 == tmp2) {
                return tmp1;
            }
            tmp1 = tmp1.next;
            tmp2 = tmp2.next;
        }

        return null;
    }

    /**
     * 哈希表: 俩链表相交时, 节点是同一个对象
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Set<ListNode> visited = new HashSet<>();
        ListNode node = headA;
        while (node != null) {
            visited.add(node);
            node = node.next;
        }
        node = headB;
        while (node != null) {
            if (visited.contains(node)) {
                return node;
            }
            node = node.next;
        }

        return null;
    }

    /**
     * 双指针
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }

        return pA;
    }
}
